package q1608_specialArray;

import java.util.Arrays;

public class Solution {
    /*
    按照题目的要求，该特殊值只能是1 - n中的一个数
    那么可以将数组排序后，按顺序遍历，然后比较在nums[n - i - 1]和nums[n - i]之间是否有一个数i能够满足要求
    此题也可以使用二分法去查找对应的答案
    但是时间复杂度的瓶颈主要在于排序上为nlogn，因此此后的顺序遍历时间复杂为n 不影响最后的复杂度
     */
    public int specialArray(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        if (nums[0] >= n) return n;
        for (int i = 1; i < n; ++i) {
            if (nums[n - i] >= i && nums[n - i - 1] < i) return i;
        }
        return -1;
    }
}
